class Solution {
    public:
        bool isMatch(string s, string p) {
                    // dp[i][j]表示字符串p的[0, j]区间和字符串s的[0, i]区间是否可以匹配
                            int m = s.size(), n = p.size();
                                    s = " " + s, p = " " + p;
                                            vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
                                                    dp[0][0] = true;
                                                            for(int j = 2; j <= n; j += 2)
                                                                    {
                                                                                    if(p[j] == '*')
                                                                                                    dp[0][j] = true;
                                                                                                                else
                                                                                                                                break;
                                                                    }
                                                                            for(int i = 1; i <= m; ++i)
                                                                                    {
                                                                                                    for(int j = 1; j <= n; ++j)
                                                                                                                {
                                                                                                                                    if(s[i] == p[j] || p[j] == '.')
                                                                                                                                                    {
                                                                                                                                                                            dp[i][j] = dp[i - 1][j - 1];
                                                                                                                                                    }
                                                                                                                                                                    else if(p[j] == '*')
                                                                                                                                                                                    {   // j-1为点 或者 和s[i]相等才可以匹配dp[i - 1][j]
                                                                                                                                                                                                        if(p[j - 1] == '.' || p[j - 1] == s[i])
                                                                                                                                                                                                                                dp[i][j] = dp[i][j - 2] || dp[i - 1][j];
                                                                                                                                                                                                                                                    else // 匹配空串的
                                                                                                                                                                                                                                                                            dp[i][j] = dp[i][j - 2];
                                                                                                                                                                                                                                                                                            }
                                                                                                                }
                                                                                    }
                                                                                            return dp[m][n];
        }
};
                                                                                                                                                    }
                                                                                                                }
                                                                                    }
                                                                    }
        }
}